package Datastruct.Array;


/**
 * 数据结构稀疏数组
 */
public class SparseArray {

    public static void main(String[] args) {
        //先定义一个二维数组
        int [][] arrays=new int[11][11];
        //给数组赋值
        arrays[1][2]=1;
        arrays[2][4]=2;
        arrays[3][6]=3;

        int sum=0;    //o用来计算稀疏数组当中的有效个数
        //遍历当前数组
        System.out.println("二维稀疏数组如下：");
        for (int[] array : arrays) {
            for (int  entity: array) {
                System.out.printf("%d\t",entity);
                if(entity!=0){
                    sum++;
                }
            }
            System.out.println();
        }
        System.out.println(sum);

        /**
         * 将数组进行压缩
         *
         * 先创建一个稀疏数组  第一行不存储有效数据     第一行第一列存储 原来数组的行数 第二列存储列数  第三列存储有效个数
         *
         */

        int [][]sparse=new int[sum+1][3];       //压缩后的数组
        sparse[0][0]=11;
        sparse[0][1]=11;
        sparse[0][2]=sum;

        int count=1;
        for(int i=0;i<11;i++){
            for (int j=0;j<11;j++){
                if(arrays[i][j]!=0){
                    sparse[count][0]=i;
                    sparse[count][1]=j;
                    sparse[count][2]=arrays[i][j];
                    count++;
                }
            }
        }

        System.out.println("输出压缩后的数组  第一行第一列是原来数组的行数，第二列是列数 第三列是有效个数");
        for (int[] ints : sparse) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }

        /**
         * 将压缩后的数组还原稀疏数组
         * 新建一个二维数组
         */

        int[][] newarr=new int[sparse[0][0]][sparse[0][1]];
        for(int i=1;i<count;i++){

                newarr[sparse[i][0]][sparse[i][1]] = sparse[i][2];

        }
        System.out.println("压缩数组返回的稀疏数组如下：");
        for (int[] ints : newarr) {
            for (int anInt : ints) {
                System.out.printf("%d\t",anInt);
            }
            System.out.println();
        }


    }

}
